#pragma once
#include<iostream>
using namespace std;

namespace code
{
	//节点
	template<class T>
	struct node 
	{
		node(const T& val = T())
			:_prev(nullptr)
			,_next(nullptr)
			,_val(val) 
		{}

		node<T>* _prev;
		node<T>* _next;
		T _val;
	};

	//迭代器
	template<class T, class Ref, class Ptr>
	struct Iterator 
	{
		typedef node<T> node;
		typedef Iterator<T, Ref, Ptr> Self;
		//成员函数
		Iterator(node* node = nullptr)
			:_pnode(node)
		{}

		//模拟指针
		Ref operator*() 
		{
			return _pnode->_val;
		}

		Ptr operator->() 
		{
			return &(_pnode->_val);
		}

		Self& operator++() 
		{
			_pnode = _pnode->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}

		Self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		Self operator--(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}


		bool operator!=(Self it) 
		{
			return _pnode != it._pnode;
		}

		bool operator==(Self it)
		{
			return _pnode == it._pnode;
		}

		//成员变量
		node* _pnode;
	};

	//链表
	template<class T>
	class list 
	{
		typedef node<T> node;
		typedef Iterator<T, T&, T*> iterator;
		typedef Iterator<T, const T&, const T*> const_iterator;


	public:
		//1.默认成员函数
		void init() 
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		list() 
		{
			init();
		}

		list(int n, const T& value = T()) 
		{
			init();
			while (n--) 
			{
				push_back(value);
				++_size;
			}
		}

		template <class Iterator>
		list(Iterator first, Iterator last) 
		{
			init();
			while (first != last) 
			{
				push_back(*first);
				++first;
				++_size;
			}
		}

		list(const list<T>& lt)				 //拷贝构造
		{
			init();
			auto it = lt.begin();
			while (it != lt.end()) 
			{
				push_back(*it);
				it++;
				_size++;
			}
		}

		list<T>& operator=(list<T> lt)		//赋值
		{
			swap(lt);
			return *this;
		}

		void swap(list<T>& lt) 
		{
			std::swap(_head,lt._head);
			std::swap(_size, lt._size);
		}

		~list()								//析构
		{
			clear();
			delete _head;
			_size = 0;
		}

		void clear() 
		{
			auto it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		//2.访问
		//2.1 迭代器
		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}

		const_iterator end()const
		{
			return const_iterator(_head);
		}

		//2.2 front 与 back()
		T& front()
		{
			return *begin();
		}

		const T& front() const
		{
			return *begin();
		}

		T& back()
		{
			return *(--end());
		}

		const T& back()const
		{
			return *(--end());
		}

		//2.3容量
		size_t size()const
		{
			return _size;
		}

		bool empty()const
		{
			return _head->_next == _head;
		}



		//其它
		void print()
		{
			auto it = begin();
			while (it != end())
			{
				cout << *it << " ";
				++it;
			}
			cout << endl;
		}

		//3.修改
		void push_back(const T& val)
		{
			insert(end(), val);
		}
		
		void pop_back() 
		{
			erase(--end());
		}

		void insert(iterator pos, const T& val)
		{
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* newnode = new node(val);

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			_size++;
		}

		iterator erase(iterator pos) 
		{
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;
			delete cur;
			_size--;

			return iterator(next);
		}


	private:
		node* _head;
		size_t _size = 0;
	};


	void test1() 
	{
		list<int> l1;
		l1.push_back(1); l1.push_back(2); l1.push_back(3);
		cout << "l1: "; l1.print();

		list<int> l2(l1);
		cout << "l2(l1): "; l2.print();

		list<int> l3;
		l3.push_back(3); l3.push_back(2); l3.push_back(1);
		cout << "l3: "; l3.print();

		l2 = l3;
		cout << "l2 = l3: "; l2.print();

		list<int> l4(5,1);
		cout << "l4(5,1): "; l4.print();

		list<int> l5(l4.begin(), l4.end());
		cout << "l5(l4.begin(), l4.end()): "; l5.print();
	}

	void test2()
	{
		list<int> l1;
		l1.push_back(1); l1.push_back(2); l1.push_back(3); l1.push_back(4);
		cout << "l1: "; l1.print();

		cout << "范围for: ";
		for (auto node : l1) 
		{
			cout << node << " ";
		}

		cout << endl;
		cout << "l1.size(): " << l1.size() << endl;

		cout << "l1.empty(): " << l1.empty() << endl;

		cout << "l1.front(): "  <<l1.front() << endl;

		cout << "l1.back(): " << l1.back() << endl;

	}

	void test3() 
	{
		list<int> l1;
		l1.insert(l1.begin(), 1);
		l1.insert(++l1.begin(), 2);
		cout << "l1.insert(): "; l1.print(); 

		l1.erase(l1.begin());
		cout << "l1.erase(): "; l1.print(); 

		l1.push_back(4);
		cout << "l1.push_back(4): "; l1.print(); 

		l1.pop_back();
		cout << "l1.pop_back(): "; l1.print(); 

		l1.clear();
		cout << "l1.clear(): "; l1.print(); cout << endl;

	}
}